home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Magnum One
/
Magnum One (Mid-American Digital) (Disc Manufacturing).iso
/
d18
/
mrgsort.arc
/
MRGSORT.PAS
< prev
next >
Wrap
Pascal/Delphi Source File
|
1990-04-18
|
5KB
|
121 lines
UNIT mrgsort;
(* By C.B. Falconer, public domain. This is based on a description *)
(* in Sedgewicks 'Algorithms', but modified for isolation to a TP *)
(* unit, with a generalized linkage to the items to sort. *)
(* Since the 'info' field of a linknode is never used here, the *)
(* actual record may be designed as the application demands, so *)
(* long as the FIRST item in it is the 'next' pointer. Care must *)
(* then be taken not to modify the info field of 'null'. *)
(* The user defined 'greater' function will receive whatever type *)
(* of pointer is passed in to sort, and never the null pointer. *)
(* The list to be sorted must be terminated with a 'next' that *)
(* contains the value 'null', and it must be the null defined here. *)
INTERFACE
TYPE
greaterf = FUNCTION(thing, than : pointer) : boolean;
VAR
null : pointer; (* used as NIL substitute for end marks *)
FUNCTION sort(root : pointer; greater : greaterf) : pointer;
(* This provides a logical level for passing in the 'greater' proc. *)
(* note that these procedures do not use the header link, i.e. the *)
(* pointers they receive carry actual list data. The pointers will *)
(* later be defined as holding only the next and an 'info' pointer. *)
(* The info pointer will not be used here, so can be of any type. *)
IMPLEMENTATION
TYPE
link = ^linknode;
linknode = RECORD
next : link;
(* Actual items have information following 'next' *)
END;
(* 1---------------1 *)
FUNCTION sort(root : pointer; greater : greaterf) : pointer;
(* 2---------------2 *)
FUNCTION msort(root : link) : link; (* RECURSIVE *)
(* The use of the terminal sentinal 'null' with null^.next = null *)
(* is especially handy in the split process. This avoids having *)
(* any special processing to handle the list ends. *)
(* The critical thing for using generalized pointers is that the *)
(* FIRST field in the record should be the 'next' pointer. This *)
(* code uses nothing else outside the 'greater' function. *)
(* Stack usage per recursion level should be 4 pointers and one *)
(* near stack marker, or about 22 bytes per level. Sorting 65000 *)
(* items thus should not require over 352 bytes of stack. (TP5) *)
VAR
left, right : link;
(* 3---------------3 *)
FUNCTION merge(a, b : link) : link;
(* here we temporarily reuse null as a list header, *)
(* in addition to its normal use as a terminator. *)
(* Care is taken to NEVER pass null to 'greater'. *)
VAR
c : link;
BEGIN (* merge *)
c := null; (* null^.next holds start of list for now *)
REPEAT
(* WARNING - short circuit evaluation assumed here *)
{} IF (b = null) OR ((a <> null) AND greater(b, a)) THEN BEGIN
c^.next := a; c := a; a := a^.next; END
ELSE BEGIN
c^.next := b; c := b; b := b^.next; END;
UNTIL c = null;
merge := link(null)^.next;
link(null)^.next := null; (* restore null *)
END; (* merge *)
(* 3---------------3 *)
PROCEDURE split(root : link; VAR left, right : link);
(* splits the list into two null terminated lists *)
BEGIN (* split *)
left := root; (* this is all settled *)
right := root^.next^.next^.next;
WHILE right <> null DO BEGIN
(* advance the left pointer 1, the right pointer 2 *)
root := root^.next; right := right^.next^.next; END;
right := root^.next; (* this has moved halfway *)
root^.next := null; (* and terminate the left list *)
END; (* split *)
(* 3---------------3 *)
BEGIN (* msort *)
IF root^.next = null THEN msort := root
ELSE BEGIN
split(root, left, right);
msort := merge(msort(left), msort(right)); END;
END; (* msort *)
(* 2---------------2 *)
BEGIN (* sort *)
sort := link(msort(link(root)));
END; (* sort *)
(* 1---------------1 *)
BEGIN (* mrgsort initialization *)
new(link(null)); link(null)^.next := null;
END. (* mrgsort initialization *)
½@